A major category of SHM techniques involves model-based methods, which typically use a physics-based model of the structure in its healthy state and apply various techniques to identify the presence, location, severity, and type of potential damage. However, these methods can be time-consuming, prompting the integration of machine learning techniques due to their efficiency and computational effectiveness. In this study, we propose a method that applies Graph Neural Networks (GNNs) and Finite Element (FE) models to improve the accuracy of damage localization in structures. We developed an FE model of the Louisville Bridge, a steel truss structure, and introduced various random damage scenarios to determine the mode shapes of the structure under 1000 different damage scenarios. The damage is considered as reduction in the stiffness of the elements, ranging from 0 to 30% in different members. A multilayer perceptron (MLP) network then was trained to classify each element as damaged or healthy, using input features such as the values of the first five mode shapes at both ends of the members, the degree of axis, and the length of each element. Subsequently, we created a line graph model of the bridge, where each node represents a structural member, and each edge represents a joint in the truss bridge. The GNN was then trained, incorporating the MLP outputs as input features in graph nodes, to detect damaged elements by combining the information from the MLP with the inherent topological relationships encoded in the graph model. The trained model was tested under scenarios with 5% noise to assess its robustness. The results indicate that this method significantly outperforms competitive approaches, such as mode shape energy-based methods and standalone MLP models.